package com.yangzhe.algorithm.c041;

// 一个正整数如果能被 a 或 b 整除，那么它是神奇的。
// 给定三个整数 n , a , b ，返回第 n 个神奇的数字。
// 因为答案可能很大，所以返回答案 对 1000000007 取模
// 测试链接 : https://leetcode.cn/problems/nth-magical-number/
public class Code02_NthMagicalNumber {

    /**
     * 思路： 二分法答案法 容斥原理
     * 设答案第 n 个神奇的数字是kn，
     * 1. 则 kn < n * min(a , b)，
     * 比如 a = 2, b = 3, n = 100，如果只有a存在，答案一定在 2 * 100 = 200 内找到，增加一个b则可以加速找到答案的过程
     * 2. 容斥原理：前 x 个正整数中有多少个“神奇数字”
     * f(x) = x / a + x / b - x / lcm(a, b)
     * 3. 二分法
     *
     * @param n
     * @param a
     * @param b
     * @return
     */
    public static int nthMagicalNumber(int n, int a, int b) {
        long l = 0;
        long r = (long) n * Math.min(a, b);
        long m = 0;
        long result = 0;
        // 二分
        while (l <= r) {
            m = (l + r) / 2;
            // 容斥原理，计算[0, m]神奇数字的个数
            long magicNumCount = m / a + m / b - m / lcm(a, b);
            if (magicNumCount < n) {
                // 不够，则继续在右侧查找
                l = m + 1;
            } else {
                // 第 n 个神奇数字就是最小的那个，个数够也要继续向左二分，直到找到最小的数字
                r = m - 1; // 继续往左找更小的可能
                result = m; // 记录当前可行解
            }
        }
        return (int) (result % ((int) Math.pow(10, 9) + 7));
    }

    public static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        } else {
            return gcd(b, a % b);
        }
    }

    public static int lcm(int a, int b) {
        return (a * b) / gcd(a, b);
    }

    public static void main(String[] args) {
        int a = 4;
        int b = 6;
        int n = 3;
        System.out.println("Magic number:" + nthMagicalNumber(n, a, b));
    }
}
